from typing import List


class Solution:
    """
    45. 跳跃游戏 II
    给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
    每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
    0 <= j <= nums[i]
    i + j < n
    返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
    """

    def jump(self, nums: List[int]) -> int:
        """
        题目分析：
        1、求最少步数到达终点。
        2、不管怎么跳是最优解，都是从0索引位置，开始往后跳。所以，只要从0索引开始，找到每一步的最远距离，就可以。
        逻辑修复：应该是从每一步的起始点，去找到后面的那几步，找到哪一步能走的更远，如果找到了，那个就是新的起始点
        解题思路：
        i控制外层循环，每一步的起始点
        j控制内层循环，每一个起始点，能往后走的所有可能
        """
        if len(nums) == 1:
            jumps = []
            return jumps.__len__()
        start = 0
        jumps = []
        n_len = len(nums)
        while start < n_len:
            print('start:', start)
            foot = start + 1
            # longest = start
            longest_foot = start + 1
            while foot <= start + nums[start] and foot < n_len:
                if start + nums[foot] > longest_foot:
                    # 对比每一个下一步之后能走的最远距离，对比找出下一步之后能走最远的那个
                    longest_foot = foot
                    longest = start + nums[foot]
                print('foot:', foot, 'longest_foot:', longest_foot)
                foot += 1
            jumps.append(longest_foot)
            start = longest_foot  # 更新，下一步的起始点
            if longest_foot >= len(nums) - 1:
                break
        print(jumps)
        return jumps.__len__()

    def jump_002(self, nums: List[int]) -> int:
        """
        思路跟看大牛写的差不多，但是上面的代码就是不够用。
        看完大神代码后，再重新写
        public int jump(int[] nums) {
            int n = nums.length;
            int curL = 0, curR = 0, ans = 0; // curL: 当前可移动的左端点，curR: 当前可移动的右端点，初始时在0号位置，可以理解为移动区间为[0,0]
            while (curR < n - 1) {  // 当可移动的区间又端点没能达到nums.length-1
                int l = curL, r = curR;
                for (int i = l; i <= r; i++){ // 遍历当前可移动区间的所有位置，找到最大的右端点
                    if (nums[i] + i > curR) {
                        curR = nums[i] + i; // 更新可移动区间的左端点和右端点
                        curL = i;
                    }
                }
                ans++;
            }
            return ans;
        }
        """
        n = len(nums)
        curr_l = 0
        curr_r = 0
        steps = 0
        while curr_r < n - 1:
            l = curr_l
            r = curr_r
            i = l
            while i <= r:
                if i + nums[i] > curr_r:
                    curr_r = i + nums[i]
                    curr_l = i
                i += 1
            steps += 1
        """
        【答疑】
        问：为什么代码只需要遍历到 n−2？【step+=1在遍历的最后一定会执行，所以遍历到n-2的时候，也会再加一步。假设：nums=[1,1,1,0,1]，这种情况curr_r < n - 1就行不通，但是题目保证了一定能到达n-1，所以不用担心】
        答：当 i=n−2 时，如果 i<curRight，说明可以到达 n−1；如果 i=curRight，我们会造桥，这样也可以到达 n−1。所以无论是何种情况，都只需要遍历到 n−2。或者说，n−1 已经是终点了，你总不能在终点还打算造桥吧？
        问：我能想出这题的思路，就是代码实现总是写不对，有没有什么建议？【重要，实用，适合自己当前水平的实际情况】
        答：清晰的变量名以及一些必要的注释，会对理清代码逻辑有帮助。在出现错误时，可以用一些小数据去运行你的代码，通过 print 或者打断点的方式，查看这些关键变量的值，看看是否与预期结果一致。
        问：如果题目没有保证一定能到达 n−1，代码要怎么改？
        """
        return steps


if __name__ == '__main__':
    s = Solution()
    # nums = [2, 3, 1, 1, 4]
    # nums = [0]
    # nums = [2, 1]
    # nums = [1, 2, 3]
    nums = [3, 2, 1]
    result = s.jump(nums)
    print('result:', result)
